package aws;

import java.util.Arrays;
public class ThreeSumClosest {
    /**
     * 最接近的三数之和
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int result=Integer.MAX_VALUE;
            //
            int reduce = Integer.MAX_VALUE;
            //最接近的差值
            int closest = Integer.MAX_VALUE;

            for(int index = 0; index < nums.length - 1; index++) {
                int num1 = nums[index];
                int i = index+1;
                int j = nums.length -1;
                while(i < j) {
                    int num2 = nums[i];
                    int num3 = nums[j];
                    int sum = num1 + num2 + num3;
                    //三数字之和与target的差值
                    reduce = Math.abs(sum - target);
                    if(reduce == 0) {
                        return target;
                    }
                    if(reduce < closest ) {
                        closest = reduce;
                        result = sum;
                    }
                    if(sum > target) {
                        j--;
                    }
                    if(sum < target) {
                        i++;
                    }
                }


            }
            return result;
    }
}
